package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/20 11:45
 **/
public class Day35_2_Num654_ConstructMaximumBinaryTree {
    class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            return dfs(nums,0,nums.length-1);
        }
        private TreeNode dfs(int[] nums, int left, int right){
            if(left > right) return null;
            if(left == right) return new TreeNode(nums[left]);

            int index = findMax(nums, left, right);
            TreeNode cur = new TreeNode(nums[index]);
            cur.left = dfs(nums, left, index-1);
            cur.right = dfs(nums, index+1,right);
            return cur;
        }
        // 找到最大值索引
        private int findMax (int[] nums, int left, int right){
            int maxIndex = 0, maxValue = 0;
            for(int i = left; i <= right; ++i){
                if(nums[i] > maxValue) {
                    maxValue = nums[i];
                    maxIndex = i;
                }
            }
            return maxIndex;
        }
    }
}